\section{Pell 型方程}
Pell 方程是由 Euler 提出的不定方程， 原指
\[
x^{2}-d y^{2}=1
\]
其中 $d$ 为无平方因子的正整数。 现也指 $x^{2}-d y^{2}= \pm 1$, 或 $x^{2}-d y^{2}= \pm 4$. 自古多有研究。 后来发现， 它们决定实二次数域的单位。 它们密切相关于如下 Pell 型 (Pell-like) 方程：
\[
x^{2}-d y^{2}=c
\]
这里都是要求非零的整数解， 事实上只需求出正 (整数) 解。

注意 $x^{2}-d y^{2}=c$ 可以写为
\[
N(x+\sqrt{d} y)=(x+\sqrt{d} y)(x-\sqrt{d} y)=c
\]
故若 $(x, y)$ 为解， 则也称 $x+\sqrt{d} y$ 为其解。 当 $x, y$ 互素时称为本原 (primitive)解， 当 $x, y$ 为正时称为正解 $\beta=x+\sqrt{d} y$ 的范数定义为 $N(\beta)=x^{2}-d y^{2}$. 注意范数是积性函数 (与 Gauss 数的范数类似):
\[
N(\beta \gamma)=N(\beta) N(\gamma)
\]
$\beta^{\prime}=x-\sqrt{d} y$ 称为 $x+\sqrt{d} y$ 的共轭。 故原方程也可记为 $N(\beta)=c$, 或 $\beta \beta^{\prime}=c$.

由 $\S 6.3$ 定理 4 知 $\sqrt{d}$ 的连分数的渐近分数 $p_{n} / q_{n}$ 满足
\[
p_{n-1}^{2}-d q_{n-1}^{2}=(-1)^{n} Q_{n}
\]
故若 $c=(-1)^{n} Q_{n}$, 则 $\left(p_{n-1}, q_{n-1}\right)$ 是方程的解。 注意 $\sqrt{d}$ 的连分数是循环的， 设
\[
  \sqrt{d} = \left[ a_0, \overline{a_1,\cdots,a_1,2a_0} \right] = \left[a_0, \overline{a_1,\cdots,a_{m-1},a_m}\right]
\]
满足此式的最小 $m$ 称为 $\sqrt{d}$ 的连分数的循环周期。 此时， $t_{n}=t_{n+k m}$ (对整数 $k \geqslant$ $0)$ ，即
\[
\left(P_{n}+\sqrt{d}\right) / Q_{n}=\left(P_{n+k m}+\sqrt{d}\right) / Q_{n+k m}
\]
故 $a_{n}, t_{n}, P_{n}, Q_{n}$ 都是循环的。

\begin{theorem}%定理1
考虑 Pell 型方程 $x^{2}-d y^{2}=c$. 设 $\sqrt{d}$ 的连分数如上， 周期为 $m$.

 (1) 若 $c=(-1)^{n} Q_{n}$, 则此方程有整数解 $\left(p_{n-1}, q_{n-1}\right)$. 且
\[
p_{n-1+k m}^{2}-d q_{n-1+k m}^{2}=(-1)^{n+k m} Q_{n} \quad(\text { 对整数 } k \geqslant 0) .
\]

 (2) 若 $c \neq(-1)^{n} Q_{n}$ 且 $|c|<\sqrt{d}$, 则 $x^{2}-d y^{2}=c$ 无整数解。
\end{theorem}

\begin{proof}
 (1) 由上述显然。 (2) 由 §6.2 定理 6 即得。
\end{proof}

例如， $d=19$ 时， $m=6,\left(Q_{0}, \cdots, Q_{6}\right)=(1,3,5,2,5,3,1)$, 故 $c=$ $-3,5,-2,1$ 时有解， 解分别为 $(4,1),(9,2),(13,3),(170,39)$.

\begin{theorem}%定理2
考虑 Pell 方程 $x^{2}-d y^{2}= \pm 1$. 设 $\sqrt{d}$ 的连分数如上， 周期为 $m$.

 (1)  $x^{2}-d y^{2}=1$ 有无限多解。 其最小正解为
\[
p_{m-1}+\sqrt{d} q_{m-1} \text { 或 } \quad p_{2 m-1}+\sqrt{d} q_{2 m-1} \text { （依 } m \text { 为偶数或奇数）. }
\]
其全部正解为
\[
p_{k m-1}+\sqrt{d} q_{k m-1} \text { 或 } \quad p_{2 k m-1}+\sqrt{d} q_{2 k m-1} \text { （依 } m \text { 为偶数或奇数） }
\]
( $k$ 为正整数。 正解是指 $x, y$ 为正整数).

 (2) 对 $x^{2}-d y^{2}=-1$, 当 $m$ 为奇数时有无限多解， 其全部正解为
\[
p_{k m-1}+\sqrt{d} q_{k m-1} \text { ( } k \text { 为正奇数). }
\]
而当 $m$ 为偶数时， $x^{2}-d y^{2}=-1$ 无解。
\end{theorem}

\begin{proof}
 定理中给出的显然确实为解。 反之， 若 $(x, y)$ 是 $x^{2}-d y^{2}= \pm 1$ 的正解， 则因 $\left|x^{2}-d y^{2}\right|=1<\sqrt{d}$, 由 $\S 6.2$ 定理 6 知， $x / y=p_{n-1} / q_{n-1}$ 必是 $\sqrt{d}$ 的连分数的某渐近分数， 即解必为 $p_{n-1}+\sqrt{d} q_{n-1}$. 于是 (由 $\S 6.3$ 定理 4 ) 有
\[
\pm 1=p_{n-1}^{2}-d q_{n-1}^{2}=(-1)^{n} Q_{n}
\]
即 $\pm 1=(-1)^{n} Q_{n}$. 这首先意味着 $Q_{n}=1$, 这当且仅当 $n=k m$ （整数 $k \geqslant 0$ ）. 这是因为， $Q_{n}=1$ 意味着尾项
\[
t_{n}=\left(P_{n}+\sqrt{d}\right) / Q_{n}=P_{n}+\sqrt{d}=\left(P_{n}+a_{0}\right)+\left(\sqrt{d}-a_{0}\right)
\]
从而 $t_{n+1}=1 /\left(\sqrt{d}-a_{0}\right)=t_{1}$, 进人循环。 其次需看 $n=k m$ 的奇偶性， 决定
\[
(-1)^{n}=(-1)^{k m}=1 \text { 或 }-1.
\]
若 $m$ 为偶数， 则总有 $(-1)^{k m}=1$. 若 $m$ 为奇数， 则 $(-1)^{k m}=1$ 或 -1 (依 $k$ 取偶数或奇数）.

将证明：当 $d$ 为素数， $p \equiv 1(\bmod 4)$ 时， 周期 $m$ 为奇数。

例如， $d=13$ 时， $m=5, \sqrt{13}=[3, \overline{1,1,1,1,6}],\left(Q_{0}, \cdots, Q_{5}\right)=(1,4$, $3,3,4,1)$. 而 $p_{0} / q_{0}$ 到 $p_{9} / q_{9}$ 为： $3 / 1,4 / 1,7 / 2,11 / 3,18 / 5,119 / 33$, $137 / 38,256 / 71,393 / 109,649 / 180$.

故 $x^{2}-13 y^{2}=-1$ 的最小正解为 $\left(p_{4}, q_{4}\right)=(18,5)$.

而 $x^{2}-13 y^{2}=1$ 的最小正解为 $\left(p_{9}, q_{9}\right)=(649,180)$.

对 Pell 方程 $x^{2}-d y^{2}=-1$, 若 $\beta=x+\sqrt{d} y$ 是其解， 则意味着
\[
N(\beta)=\beta \beta^{\prime}=x^{2}-d y^{2}=-1
\]
于是
\[
N\left(\beta^{2}\right)=N(\beta)^{2}=\left(\beta \beta^{\prime}\right)^{2}=1
\]
即 $\beta^{2}$ 是 $x^{2}-d y^{2}=1$ 的解。 类似可知， $\beta^{3}$ 是 $x^{2}-d y^{2}=-1$ 的解， 等等。 对正解 (即 $x$, $y$ 为正整数), 显然 $\beta<\beta^{2}<\beta^{3}<\cdots$. 这从另一角度说明了， 存在 $x^{2}-d y^{2}=-1$ 的最小正解 $\varepsilon$ (称为基础解). 对 $x^{2}-d y^{2}=1$ 也同样。
\end{proof}

\begin{theorem}%定理3
设 $\varepsilon=x_{1}+\sqrt{d} y_{1}$ 为 $x^{2}-d y^{2}=e(e= \pm 1)$ 的基础解（即 $\varepsilon$ 是 $x^{2}-d y^{2}=1$ 或 $x^{2}-d y^{2}=-1$ 的正解 (指 $x, y$ 为正整数), 且在所有正解中最小).

 (1) 若 $N(\varepsilon)=1$, 即若 $\varepsilon$ 是 $x^{2}-d y^{2}=1$ 的（基础）解， 则 $x^{2}-d y^{2}=1$ 的所有解为
\[
x_{k}+\sqrt{d} y_{k}= \pm \varepsilon^{k}= \pm\left(x_{1}+\sqrt{d} y_{1}\right)^{k} \quad(k \in \mathbb{Z})
\]
而 $x^{2}-d y^{2}=-1$ 无解。

 (2) 若 $N(\varepsilon)=-1$, 即若 $\varepsilon$ 是 $x^{2}-d y^{2}=-1$ 的（基础）解， 则 $x^{2}-d y^{2}= \pm 1$ 的所有解为
\[
x_{k}+\sqrt{d} y_{k}= \pm \varepsilon^{k}= \pm\left(x_{1}+\sqrt{d} y_{1}\right)^{k} \quad(k \in \mathbb{Z})
\]
其中偶数 $k$ 给出 $x^{2}-d y^{2}=1$ 的解， 奇数 $k$ 给出 $x^{2}-d y^{2}=-1$ 的解。
\end{theorem}

\begin{proof}
 显然， 定理中的 $x_{k}+\sqrt{d} y_{k}$ 确实是解：
\[
x_{k}^{2}-d y_{k}^{2}=N\left(x_{k}+\sqrt{d} y_{k}\right)=N(\varepsilon)^{k}=( \pm 1)^{k}
\]
只需再证明定理给出了全部的解。 假设 $u^{2}-d v^{2}=e$, 而 $(u, v)$ 不是定理给出的 $\left(x_{k}, y_{k}\right)$; 可设 $\beta=u+v \sqrt{d}$ 最小 (对具有这种性质的正整数对), 则存在 $k$ 使
\[
\varepsilon^{k}<\beta<\varepsilon^{k+1}, \quad \varepsilon^{k-1}< \pm \beta \varepsilon^{\prime}<\varepsilon^{k}
\]
后者是因为 $\varepsilon \varepsilon^{\prime}=\left(x_{1}+\sqrt{d} y_{1}\right)\left(x_{1}-\sqrt{d} y_{1}\right)= \pm 1$. 于是
\[
\varepsilon^{k-1}< \pm \beta \varepsilon^{\prime}<\varepsilon^{k}<\beta<\varepsilon^{k+1}
\]
注意 $N\left( \pm \beta \varepsilon^{\prime}\right)=N(\beta) N\left(\varepsilon^{\prime}\right)= \pm 1$, 故 $\pm \beta \varepsilon^{\prime}=u^{\prime}+v^{\prime} \sqrt{d}$ 也是解。 而由 $\beta$ 的最小性可知， 应有 $\pm \beta \varepsilon^{\prime}=\varepsilon^{s}$ 是定理中给出的解， 从而 $\beta=\varepsilon^{s+1}$ 也是定理给出的解。
\end{proof}

由上述定理可知， 用连分数求解 $x^{2}-d y^{2}= \pm 1$ 的具体方法： 将 $\sqrt{d}$ 逐步展开为连分数， 首次出现 $Q_{n}=1$ 时， 此 $n=m$ 即为周期。 此时注意：

(1) 若 $m$ 为偶数， 则 $\varepsilon=p_{m-1}+\sqrt{d} q_{m-1}$ 为 $x^{2}-d y^{2}=1$ 的基础解， 其全部解为 $\pm \varepsilon^{k}(k \in \mathbb{Z})$, 而 $x^{2}-d y^{2}=-1$ 无解。

 (2) 若 $m$ 为奇数， 则 $\varepsilon=p_{m-1}+\sqrt{d} q_{m-1}$ 为 $x^{2}-d y^{2}=-1$ 的基础解， 其全部解为 $\pm \varepsilon^{k}$ ( $k$ 为奇数). 而 $x^{2}-d y^{2}=1$ 的基础解为
\[
\varepsilon_{+}=p_{2 m-1}+\sqrt{d} q_{2 m-1}
\]
其全部解为 $\pm \varepsilon_{+}^{k}(k \in \mathbb{Z})$.

对 Pell 型方程 $x^{2}-d y^{2}=c$, 当 $|c|<\sqrt{d}$ 时可由连分数方法完全解决(定理 1).对 $|c|>\sqrt{d}$ 情形， 也有用连分数的解法。 此时任一本原解 $\sigma=x_{0}+y_{0} \sqrt{d}$ 对应于唯一的
\[
\tau=x_{1}+y_{1} \sqrt{d}
\]
满足条件
\[
\sigma^{\prime} \tau=\left(x_{0}-y_{0} \sqrt{d}\right)\left(x_{1}+y_{1} \sqrt{d}\right)=z+\sqrt{d}, \quad-|c| / 2<z \leqslant|c| / 2
\]
且 $|N(\tau)|<|N(\sigma)|=|c|$. 而 $x_{0}=\left(x_{1} z-y_{1} d\right) / N(\tau), y_{0}=\left(y_{1} z-x_{1}\right) / N(\tau)$.利用此对应， 可由 $\alpha=(z+\sqrt{d}) / c$ 的连分数求解原方程 (参见 [29]).

